home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / Python 1.1 / Demo / turing / parse.tm < prev    next >
Encoding:
Text File  |  1994-04-28  |  1.1 KB  |  35 lines  |  [TEXT/R*ch]
  1.  
  2. ;
  3. ; This turing machine will accept any inputs of the form 0...01...1, where
  4. ; there are an equal number of zeros and ones and will reject all other
  5. ; inputs.
  6. ;
  7. ; on return, the tape head will point to the character 'Y' if it accepts,
  8. ; and the character 'N' if it rejects.
  9. ;
  10.  
  11. <1, '0'> --> <1, '!'>    ; replace zero on the left
  12. <1, '1'> --> <0, 'N'>    ; 1 when first digit must be zero, reject
  13. <1, '!'> --> <2, R>    ; find the first 1
  14.  
  15. <2, '0'> --> <2, R>    ; skip other zero's
  16. <2, '1'> --> <3, R>    ; go to the rightmost 1.
  17. <2, ' '> --> <0, 'N'>    ; Didn't find a 1, don't accept
  18. <2, '%'> --> <0, 'N'>    ; ditto for this case
  19.  
  20. <3, '1'> --> <3, R>    ; Skip one's
  21. <3, '0'> --> <0, 'N'>    ; found a 0 mixed in, don't accept
  22. <3, '%'> --> <4, L>    ; at the rightmost 1.
  23. <3, ' '> --> <4, L>    ; ditto
  24.  
  25. <4, '1'> --> <4, '%'>    ; replace the one
  26. <4, '%'> --> <5, L>    ; and move to find a zero
  27.  
  28. <5, '1'> --> <5, L>    ; find leftmost zero
  29. <5, '0'> --> <5, L>    ; found the zero's...
  30. <5, '!'> --> <6, R>    ; in state <6> we are at the leftmost zero
  31.  
  32. <6, '0'> --> <1, '!'>    ; replace with '!' and repeat
  33. <6, '1'> --> <0, 'N'>    ; some one's are left
  34. <6, '%'> --> <0, 'Y'>    ; all one's are consumed
  35.